package com.colter.project.data.structure.graph;

import java.util.HashMap;

public class Dijstra2 {

	public static void main(String[] args) {
//		int[][] weight = { 
//				{0,40,20,9999,30},
//				{40,0,5,9999,10},
//				{20,5,0,30,9999},
//				{9999,9999,30,0,20},
//				{30,10,9999,20,9999}
//				};

		//有向图
		int[][] weight = { 
				{0,10,20,9999,30,9999},
				{9999,0,5,9999,10,9999},
				{9999,9999,0,30,9999,9999},
				{9999,5,9999,0,9999,9999},
				{9999,9999,9999,40,0,9999},
				{9999,9999,9999,9999,9999,0}
				};
		
		
		int[] path = Dijsktra(weight, 0);
		for (int i = 0; i < path.length; i++)
			System.out.print(path[i] + "  ");
		System.out.println(map);
	}
	public static HashMap<String, String> map = new HashMap<>();
	
	public static void put(int k, Object o){
		String key = String.valueOf(k);
		if(map.containsKey(key)){
			map.put(key, map.get(key) + o);
		}else{
			map.put(key, String.valueOf(o));
		}
	}
	
	public static int[] Dijsktra(int[][] weight, int start) {
		int n = weight.length;
		int[] visited = new int[n];
		int[] shortPath = new int[n];

		visited[0] = 1;
		shortPath[0] = 0;

		for (int count = 1; count <= n - 1; count++) {
			int minPath = 99999;
			int k = -1;

			// 找到未标记的顶点中，距离最小的
			for (int i = 0; i < n; i++) {
				if (visited[i] == 0 && weight[start][i] <= minPath) {
					minPath = weight[start][i];
					k = i;
				}
			}
			visited[k] = 1;
			shortPath[k] = minPath;
			put(k, k);

			// 以这个点为中间点 更新start到各个顶点的距离
			for (int i = 0; i < n; i++) {
				if (visited[i] == 0 && weight[start][k] + weight[k][i] <= weight[start][i]) {
					weight[start][i] = weight[start][k] + weight[k][i];
					put(i, map.get(String.valueOf(k)) == null ? k : map.get(String.valueOf(k)) + k);
				}
			}

		}

		return shortPath;
	} 
}